package leetcodeHis;

/**
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 *
 *
 * 输入: "cbbd"
 * 输出: "bb"
 */
public class Algo_5_最长回文子串 {
    public static void main(String[] args) {
        String input = "bb";
        System.out.println("最长回文子串"+longestPalindrome(input));
        System.out.println(1);
    }

    public static String longestPalindrome(String s) {
        //动态规划
        int length = s.length();
        boolean[][] arr = new boolean[length][length];
        int maxLen = 0 ;
        String result = "";
        if(length<=1) {
            return s;
        }
        for (int len = 1; len <= length; len++) {
            for (int start = 0; start < length; start++) {
                int end = start + len -1;
                if(end>= length) {
                    break;
                }
                arr[start][end] = ((len==1 || len==2 || arr[start+1][end-1]) && s.charAt(start) == s.charAt(end));

                if(arr[start][end] && len>maxLen) {     //如果是回文，并且
                    result = s.substring(start, end+1);
                }
            }
        }
        return result;
    }


    /**
     * 暴力法，双重循环，超时！！
     * @param s
     * @return
     */
    public static String longestPalindrome2(String s) {
        int max = 0 ;
        String result = s;

        for (int i = 0; i < s.length(); i++) {
            for (int j = s.length(); j > i; j--) {
                String child = s.substring(i,j);
                if(child.length()>max && validCircleStr(child)) {
                    max = child.length();
                    result = child;
                    if(max == s.length()) {
                        break;
                    }
                }
            }
        }
        return result;
    }

    /**
     *
     */
    public static boolean validCircleStr(String s) {
        for (int i = 0; i < s.length()/2; i++) {
            if(s.charAt(i) != s.charAt(s.length()-1-i)) {
                return false;
            }
        }
        return true;
    }
}
